{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked List Reversal - SOLUTION\n",
    "\n",
    "## Problem\n",
    "\n",
    "Write a function to reverse a Linked List in place. The function will take in the head of the list as input and return the new head of the list.\n",
    "\n",
    "You are given the example Linked List Node class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self,value):\n",
    "        \n",
    "        self.value = value\n",
    "        self.nextnode = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution\n",
    "\n",
    "Since we want to do this in place we want to make the funciton operate in O(1) space, meaning we don't want to create a new list, so we will simply use the current nodes! Time wise, we can perform the reversal in O(n) time.\n",
    "\n",
    "We can reverse the list by changing the next pointer of each node. Each node's next pointer should point to the previous node.\n",
    "\n",
    "In one pass from head to tail of our input list, we will point each node's next pointer to the previous element.\n",
    "\n",
    "Make sure to copy current.next_node into next_node **before** setting current.next_node to previous. Let's see this solution coded out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reverse(head):\n",
    "    \n",
    "    # Set up current,previous, and next nodes\n",
    "    current = head\n",
    "    previous = None\n",
    "    nextnode = None\n",
    "\n",
    "    # until we have gone through to the end of the list\n",
    "    while current:\n",
    "        \n",
    "        # Make sure to copy the current nodes next node to a variable next_node\n",
    "        # Before overwriting as the previous node for reversal\n",
    "        nextnode = current.nextnode\n",
    "\n",
    "        # Reverse the pointer ot the next_node\n",
    "        current.nextnode = previous\n",
    "\n",
    "        # Go one forward in the list\n",
    "        previous = current\n",
    "        current = nextnode\n",
    "\n",
    "    return previous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution\n",
    "\n",
    "You should be able to easily test your own solution to make sure it works. Given the short list a,b,c,d with values 1,2,3,4. Check the effect of your reverse function and maek sure the results match the logic here below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Create a list of 4 nodes\n",
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)\n",
    "d = Node(4)\n",
    "\n",
    "# Set up order a,b,c,d with values 1,2,3,4\n",
    "a.nextnode = b\n",
    "b.nextnode = c\n",
    "c.nextnode = d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's check the values of the nodes coming after a, b and c:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "print a.nextnode.value\n",
    "print b.nextnode.value\n",
    "print c.nextnode.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'value'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-45-be675f4ae643>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0md\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnextnode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'value'"
     ]
    }
   ],
   "source": [
    "d.nextnode.value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far so good. Note how there is no value proceeding the last node, this makes sense! Now let's reverse the linked list, we should see the opposite order of values!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x104bd7dd0>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "print d.nextnode.value\n",
    "print c.nextnode.value\n",
    "print b.nextnode.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'value'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-50-4057c9bc3c14>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mprint\u001b[0m \u001b[0ma\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnextnode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvalue\u001b[0m \u001b[0;31m# This will give an error since it now points to None\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'value'"
     ]
    }
   ],
   "source": [
    "print a.nextnode.value # This will give an error since it now points to None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great, now we can see that each of the values points to its previous value (although now that the linked list is reversed we can see the ordering has also reversed)\n",
    "\n",
    "## Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
